package com.mikesamuel.dateseries.shared;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import com.google.gwt.user.client.rpc.IsSerializable;

/**
 * A monotonically increasing series of dates specified by the intersection
 * points of several periodic functions.
 */
public final class DateSeries implements Iterable<Day>, IsSerializable {

  public static final class Specification implements IsSerializable {
    /**
     * The day of the week on which the week starts.
     * Sunday in the US, Monday in most of the rest of the world.
     * Regardless of WKST, days of the week are represented as integers in
     * the range [0=Sunday .. 6=Saturday] as does Date.prototype.getUTCDay().
     */
    public WeekDay wkst = WeekDay.SU;
    /** The days of the week on which dates can occur. */
    public WeekDay[] daysOfWeek = NO_WEEKDAYS;
    /** The frequency of iteration. */
    public Freq frequency = Freq.YEARLY;
    /**
     * The number of steps of length frequency that we should step forward
     * each turn of the counter.
     * There may be multiple dates within each step.
     */
    public int interval = 1;
    /**
     * The days of the month in [1..31] for exact dates, and [-1..-30] for days
     * of the month measured from the end of the month.
     */
    public int[] daysOfMonth = NO_INTS;
    /**
     * Months of the year in [1,12].
     */
    public int[] months = NO_INTS;

    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + Arrays.hashCode(daysOfMonth);
      result = prime * result + Arrays.hashCode(daysOfWeek);
      result = prime * result
          + ((frequency == null) ? 0 : frequency.hashCode());
      result = prime * result + interval;
      result = prime * result + Arrays.hashCode(months);
      result = prime * result + ((wkst == null) ? 0 : wkst.hashCode());
      return result;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj) { return true; }
      if (obj == null) { return false; }
      if (getClass() != obj.getClass()) { return false; }
      Specification other = (Specification) obj;
      return frequency == other.frequency
          && interval == other.interval
          && wkst == other.wkst
          && Arrays.equals(daysOfMonth, other.daysOfMonth)
          && Arrays.equals(daysOfWeek, other.daysOfWeek)
          && Arrays.equals(months, other.months);
    }
  }

  private Day first, iteratorLimit;
  private WeekDay wkst = WeekDay.SU;
  private WeekDay[] daysOfWeek = NO_WEEKDAYS;
  private Freq freq = Freq.YEARLY;
  private int interval = 1;
  private int[] daysOfMonth = NO_INTS;
  private int[] months = NO_INTS;

  public DateSeries(Day first, Specification spec) {
    this.first = this.iteratorLimit = first;

    if (spec != null) {
      this.wkst = spec.wkst;
      if (spec.daysOfWeek != null) {
        this.daysOfWeek = uniq(spec.daysOfWeek);
      }
      if (spec.frequency != null) {
        this.freq = spec.frequency;
      }
      this.interval = _int(spec.interval, 0, Integer.MAX_VALUE);
      if (spec.daysOfMonth != null) {
        this.daysOfMonth = uniq(_ints(spec.daysOfMonth, -31, 31));
      }
      if (spec.months != null) {
        this.months = uniq(_ints(spec.months, 1, 12));
      }
    }

    // Infer defaults.
    if (daysOfWeek.length == 0 && daysOfMonth.length == 0
        && months.length == 0) {
      switch (freq) {
        case DAILY:
          if (interval != 1) {
            daysOfWeek = WeekDay.values();
          }
          break;
        case WEEKLY:
          daysOfWeek = new WeekDay[] { first.dayOfWeek() };
          break;
        case MONTHLY:
          daysOfMonth = new int[] { first.day() };
          break;
        case YEARLY:
          months = new int[] { first.month() };
          daysOfMonth = new int[] { first.day() };
          break;
      }
    }
  }

  private DateSeries(DateSeries d, Day iteratorLimit) {
    this.first = d.first;
    this.daysOfMonth = d.daysOfMonth;
    this.daysOfWeek = d.daysOfWeek;
    this.freq = d.freq;
    this.interval = d.interval;
    this.months = d.months;
    this.wkst = d.wkst;
    this.iteratorLimit = iteratorLimit;
  }

  @SuppressWarnings("unused")
  private DateSeries() {
    // For GWT serialization during transfer.
  }

  /**
   * A compact serial format that fits in a DB row and which does not include
   * ridiculous amounts of Java serialization overhead and that works in GWT
   * without depending on GWT serialization support code.
   */
  public byte[] serialize() {
    class Bytes {
      byte[] bytes;
      int pos = 0;

      void finishSizing() {
        bytes = new byte[pos];
        pos = 0;
      }

      Bytes write(byte b) {
        if (bytes != null) {
          bytes[pos] = b;
        }
        ++pos;
        return this;
      }
      Bytes write(int s) {
        if (!(Short.MIN_VALUE <= s && s <= Short.MAX_VALUE)) {
          throw new IllegalArgumentException();
        }
        if (bytes != null) {
          bytes[pos] = (byte) (s >>> 8);
          bytes[pos+1] = (byte) (s & 0xff);
        }
        pos += 2;
        return this;
      }
      Bytes write(Day d) {
        return write(d.year()).write((byte) d.month()).write((byte) d.day());
      }
      Bytes write(int[] shorts) {
        int n = shorts.length;
        write(n);
        if (bytes != null) {
          for (int s : shorts) { write(s); }
        } else {
          pos += n * 2;
        }
        return this;
      }
      Bytes write(Enum<?>[] arr) {
        int n = arr.length;
        write(n);
        if (bytes != null) {
          for (Enum<?> e : arr) { write((byte) e.ordinal()); }
        } else {
          pos += n;
        }
        return this;
      }
    }
    Bytes out = new Bytes();
    while (true) {
      out.write((byte) 1)  // version
         .write(first)
         .write((byte) freq.ordinal())
         .write(interval)
         .write(daysOfMonth)
         .write(daysOfWeek)
         .write(months)
         .write((byte) wkst.ordinal());
      if (iteratorLimit != null) {
        out.write(iteratorLimit);
      }
      if (out.bytes != null) {
        return out.bytes;
      } else {
        out.finishSizing();
      }
    }
  }

  public static DateSeries deserialize(final byte[] bytes) {
    if (bytes[0] != 1) { throw new IllegalArgumentException(); }
    class Reader {
      int pos = 1;

      byte readByte() {
        return bytes[pos++];
      }
      short readShort() {
        short s = (short) ((bytes[pos] << 8) | (bytes[pos + 1] & 0xff));
        pos += 2;
        return s;
      }
      int[] readShortArr() {
        short n = readShort();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) { arr[i] = readShort(); }
        return arr;
      }
    }
    Reader r = new Reader();

    Day first = new Day(r.readShort(), r.readByte(), r.readByte());
    Specification spec = new Specification();
    spec.frequency = Freq.values()[r.readByte()];
    spec.interval = r.readShort();
    spec.daysOfMonth = r.readShortArr();
    spec.daysOfWeek = new WeekDay[r.readShort()];
    WeekDay[] all = WeekDay.values();
    for (int i = 0, n = spec.daysOfWeek.length; i < n; ++i) {
      spec.daysOfWeek[i] = all[r.readByte()];
    }
    spec.months = r.readShortArr();
    spec.wkst = all[r.readByte()];
    Day iteratorLimit = null;
    if (r.pos < bytes.length) {
      iteratorLimit = new Day(r.readShort(), r.readByte(), r.readByte());
    }
    DateSeries s = new DateSeries(first, spec);
    if (!first.equals(iteratorLimit)) {
      s = new DateSeries(s, iteratorLimit);
    }
    return s;
  }

  private interface MonthProducer {
    void produce(Day start, Day end, List<? super Day> out);
  }

  private interface DayProducer {
    void produce(
        int year, int month, Day start, Day end, List<? super Day> out);
  }

  public PeekingDayIterator iterator() {
    return iteratorAfter(iteratorLimit);
  }

  public PeekingDayIterator iteratorAfter(Day d) {
    DayIterator it = new DayIterator();
    it.advanceTo(d);
    return it;
  }

  /**
   * A monotonically increasing iterator over days.
   */
  public interface PeekingDayIterator extends Iterator<Day> {
    /**
     * Skip the minimum number of days necessary to ensure that the next day,
     * if any, will be on or after d.
     */
    public void advanceTo(Day d);

    /** Like next() but does not discard the next item. */
    public Day peek();

    /**
     * Produces a date series whose iterator starts in the same state as this
     * iterator at the time this method is called.
     */
    public DateSeries toDateSeries();
  }

  private final class DayIterator implements PeekingDayIterator {
    private final List<Day> pending = new ArrayList<Day>();
    private Day anchor = iteratorLimit != null ? first : null;
    private MonthProducer monthProducer =
      months.length != 0 ?
        new MonthProducer() {
          public void produce(Day start, Day end, List<? super Day> out) {
            int year = start.year();
            while (true) {
              for (int i = 0, n = months.length; i < n; ++i) {
                Day d = new Day(year, months[i], 1);
                if (d.compareTo(end) >= 0) { return; }
                out.add(d);
              }
              ++year;
            }
          }
        } :
        new MonthProducer() {
          public void produce(Day start, Day end, List<? super Day> out) {
            start = start.withDay(1);
            while (start.compareTo(end) < 0) {
              out.add(start);
              start = addPeriod(start, Freq.MONTHLY, 1);
            }
          }
        };

    private int dowBits = bitset(daysOfWeek);
    { if (dowBits == 0) { dowBits = ((1 << 7) - 1); } }
    private DayProducer dayProducer = freq == Freq.DAILY && interval != 1 ?
        new DayProducer() {
          private boolean matchesDaysOfMonth(Day d) {
            int dom = d.day();
            int nDays = DateUtil.daysInMonth(d.year(), d.month());
            for (int domf : daysOfMonth) {
              if (domf < 0) { domf += nDays + 1; }
              if (domf == dom) { return true; }
            }
            return false;
          }
          public void produce(int year, int month, Day start, Day end,
                              List<? super Day> out) {
            while (start.compareTo(end) < 0) {
              if ((dowBits & (1 << start.dayOfWeek().ordinal())) != 0) {
                if (daysOfMonth.length == 0 || matchesDaysOfMonth(start)) {
                  out.add(start);
                }
              }
              start = addPeriod(start, Freq.DAILY, interval);
            }
          }
        } : daysOfMonth.length != 0 ?
        new DayProducer() {
          public void produce(int year, int month, Day start, Day end,
              List<? super Day> out) {
            int nDays = DateUtil.daysInMonth(year, month);
            int n = daysOfMonth.length, k = 0;
            int[] absDays = new int[n];
            for (int dom : daysOfMonth) {
              if (dom < 0) { dom += nDays + 1; }
              if (dom <= 0 || dom > nDays) { continue; }
              absDays[k++] = dom;
            }
            absDays = uniq(absDays);
            for (int dom : absDays) {
              Day d = new Day(year, month, dom);
              if (d.compareTo(end) >= 0) { return; }
              if (d.compareTo(start) >= 0
                  && (dowBits & (1 << d.dayOfWeek().ordinal())) != 0) {
                out.add(d);
              }
            }
          }
        } :
        new DayProducer() {
          public void produce(int year, int month, Day start, Day end,
              List<? super Day> out) {
            Day d = year == start.year() && month == start.month()
                ? start : start.withDay(1);
            while (true) {
              for (WeekDay dow : daysOfWeek) {
                Day day = nextWeekDay(d, dow);
                if (day.month() != month || day.year() != year
                    || day.compareTo(end) >= 0) {
                  return;
                }
                if (day.compareTo(start) >= 0) {
                  out.add(day);
                }
              }
              d = addPeriod(d, Freq.WEEKLY, 1);
              if (d.compareTo(end) >= 0) { return; }
            }
          }
        };
    private void enumerate(
        Day start, Day end, List<? super Day> pending) {
      List<Day> monthsOut = new ArrayList<Day>();
      monthProducer.produce(start, end, monthsOut);
      for (Day month : monthsOut) {
        dayProducer.produce(
            month.year(), month.month(), start, end, pending);
      }
    }
    public void remove() throws UnsupportedOperationException {
      throw new UnsupportedOperationException();
    }
    public boolean hasNext() {
      fill();
      return !pending.isEmpty();
    }
    public Day peek() {
      fill();
      return pending.get(pending.size() - 1);
    }
    public Day next() {
      fill();
      return pending.remove(pending.size() - 1);
    }
    private void fill() {
      if (!pending.isEmpty() || anchor == null) { return; }
      int tries = 0;
      while (++tries < 100) {
        // Calculate next anchor.
        Day start = anchor;
        Day end = addPeriod(start, freq, 1);
        enumerate(start, end, pending);
        anchor = addPeriod(anchor, freq, interval);
        if (!pending.isEmpty()) {
          // Reverse pending in place so that next() doesn't have to do
          // ArrayList.remove(0) which is O(n).
          for (int i = 0, n = pending.size(), last = n-1, mid = n/2;
               i < mid; ++i) {
            int ip = last - i;
            Day t = pending.get(i);
            pending.set(i, pending.get(ip));
            pending.set(ip, t);
          }
          return;
        }
      }
      anchor = null;
    }
    public void advanceTo(Day d) {
      while (true) {
        Day nextAnchor = addPeriod(anchor, freq, interval);
        int delta = nextAnchor.compareTo(d);
        if (delta <= 0) {
          anchor = nextAnchor;
        }
        if (delta >= 0) {
          break;
        }
      }
      // If pending was already full, we only want to throw away those that
      // are before d.  If pending is completely emptied or was empty to begin
      // with, we want to refill it and throw away and dates before d.
      for (int j = 0; j < 2; ++j) {
        fill();
        int limit;
        for (limit = pending.size(); limit > 0; --limit) {
          if (pending.get(limit - 1).compareTo(d) >= 0) {
            break;
          }
        }
        pending.subList(limit, pending.size()).clear();
      }
    }
    @Override
    public DateSeries toDateSeries() {
      boolean hasNext = hasNext();
      return new DateSeries(DateSeries.this, hasNext ? peek() : null);
    }
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("Every ");
    if (interval != 1) { sb.append(interval).append(' '); }
    switch (freq) {
      case DAILY:   sb.append("day");   break;
      case WEEKLY:  sb.append("week");  break;
      case MONTHLY: sb.append("month"); break;
      case YEARLY:  sb.append("year");  break;
    }
    if (interval != 1) { sb.append('s'); }
    if (daysOfWeek.length != 0) {
      if (daysOfWeek.length != 7) {
        sb.append(" on ");
        if (daysOfWeek.length == 2 && WeekDay.SU == daysOfWeek[0]
            && WeekDay.SA == daysOfWeek[1]) {
          sb.append("weekends");
        } else if (daysOfWeek.length == 5 && WeekDay.MO == daysOfWeek[0]
                   && WeekDay.FR == daysOfWeek[4]) {
          sb.append("weekdays");
        } else {
          for (int i = 0, n = daysOfWeek.length; i < n; ++i) {
            if (i != 0) {
              sb.append(", ");
              if (i+1 == n) { sb.append("and "); }
            }
            sb.append(DAY_OF_WEEK_PREFIXES[daysOfWeek[i].ordinal()])
              .append("days");
          }
        }
        if (daysOfMonth.length != 0) {
          sb.append(" that are");
        }
      }
    }
    if (daysOfMonth.length != 0) {
      sb.append(" on ");
      int[] domPresentationOrder = daysOfMonth;
      // Shift the negative indices to the end.
      for (int i = 1, n = domPresentationOrder.length; i < n; ++i) {
        if (domPresentationOrder[i] >= 0) {
          domPresentationOrder = new int[n];
          for (int j = i; j < n; ++j) {
            domPresentationOrder[j - i] = daysOfMonth[j];
          }
          for (int j = 0; j < i; ++j) {
            domPresentationOrder[n - j - 1] = daysOfMonth[j];
          }
          break;
        }
      }

      for (int i = 0, n = domPresentationOrder.length; i < n; ++i) {
        if (i != 0) {
          sb.append(", ");
          if (i+1 == n) { sb.append("and "); }
        }
        int dom = domPresentationOrder[i];
        if (dom == -1) {
          sb.append("the last");
          continue;
        }
        int absDay = Math.abs(dom);
        int dayMod10 = (absDay % 10);
        int dayMod100 = (absDay % 100);
        String ordinal = "" + absDay;
        switch (dayMod100 - dayMod10 != 10 ? dayMod10 : 0) {
          case 1: ordinal += "st"; break;
          case 2: ordinal += "nd"; break;
          case 3: ordinal += "rd"; break;
          default: ordinal += "th"; break;
        }
        sb.append("the ").append(ordinal);
        if (dom < 0) { sb.append(" to last"); }
      }
      if (domPresentationOrder[domPresentationOrder.length-1] < 0) {
        sb.append(" day");
      }
      if (months.length == 0 && freq != Freq.MONTHLY) {
        sb.append(" of the month");
      }
    }
    if (months.length != 0) {
      sb.append(" of ");
      for (int i = 0, n = months.length; i < n; ++i) {
        if (i != 0) {
          sb.append(", ");
          if (i+1 == n) { sb.append("and "); }
        }
        sb.append(MONTH_NAMES[months[i]]);
      }
    }
    return sb.toString();
  }

  public Specification toSpecification() {
    Specification s = new Specification();
    s.daysOfMonth = clone(this.daysOfMonth);
    s.daysOfWeek = clone(this.daysOfWeek);
    s.frequency = this.freq;
    s.interval = this.interval;
    s.months = clone(this.months);
    s.wkst = this.wkst;
    return s;
  }

  private static int bitset(Enum<?>[] arr) {
    int bits = 0;
    for (Enum<?> e : arr) { bits = bits | (1 << e.ordinal()); }
    return bits;
  }

  private Day addPeriod(Day d, Freq f, int n) {
    return DateUtil.addPeriod(d, f, n, wkst);
  }

  private Day nextWeekDay(Day d, WeekDay wday) {
    int day = d.day();
    day -= (7 + (d.dayOfWeek().minus(wkst))) % 7;  // Shift to start of week.
    day += (7 + (wday.minus(wkst))) % 7;  // Shift forward to next wday.
    return d.withDay(day);
  }

  private static int[] uniq(int[] arr) {
    if (arr.length == 0) { return arr; }
    arr = clone(arr);
    Arrays.sort(arr);
    int last = arr[0];
    int k = 1, n = arr.length;
    for (int i = 1; i < n; ++i) {
      int curr = arr[i];
      if (last != curr) {
        arr[k++] = last = curr;
      }
    }
    if (k == n) {
      return arr;
    }
    int[] out = new int[k];
    System.arraycopy(arr, 0, out, 0, k);
    return out;
  }

  private static WeekDay[] uniq(WeekDay[] els) {
    if (els.length == 0) { return els; }
    els = clone(els);
    Arrays.sort(els);
    WeekDay last = els[0];
    int k = 1, n = els.length;
    for (int i = 1; i < n; ++i) {
      WeekDay curr = els[i];
      if (last.compareTo(curr) != 0) {
        els[k++] = last = curr;
      }
    }
    if (k == n) { return els; }
    WeekDay[] sub = new WeekDay[k];
    System.arraycopy(els, 0, sub, 0, k);
    return sub;
  }

  private static int _int(int x, int min, int max) {
    if (min <= x && x <= max) { return x; }
    throw new IllegalArgumentException(
        x + " not in [" + min + ", " + max + "]");
  }

  private static int[] _ints(int[] arr, int min, int max) {
    arr = clone(arr);
    for (int i : arr) { _int(i, min, max); }
    return arr;
  }

  private static final String[] DAY_OF_WEEK_PREFIXES = {
    "Sun", "Mon", "Tues", "Wednes", "Thurs", "Fri", "Satur"
  };

  private static final String[] MONTH_NAMES = {
    null, "Jan.", "Feb.", "Mar.", "Apr.", "May", "June", "July", "Aug", "Sep.",
    "Oct.", "Nov.", "Dec."
  };

  private static final int[] NO_INTS = new int[0];
  private static final WeekDay[] NO_WEEKDAYS = new WeekDay[0];

  private static int[] clone(int[] arr) {
    // int[].clone is not available under GWT.
    int n = arr.length;
    int[] copy = new int[n];
    System.arraycopy(arr, 0, copy, 0, n);
    return copy;
  }

  private static WeekDay[] clone(WeekDay[] arr) {
    // Object[].clone is not available under GWT.
    int n = arr.length;
    WeekDay[] copy = new WeekDay[n];
    System.arraycopy(arr, 0, copy, 0, n);
    return copy;
  }
}
